﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;

namespace Demo
{
    /// <summary>
    /// https://blog.csdn.net/mhxy199288/article/details/38025319
    /// </summary>
    public class ExpDemo
    {
        public TreeNode CreateBinaryTree(string[] expression)
        {
            var opStack = new Stack<string>();
            Queue<string> reversePolish = new Queue<string>();
            for (var i = 0; i < expression.Length; i++)
            {
                var c = expression[i];

                if (isDigitOrLetter(c))
                {
                    reversePolish.Enqueue(c);
                }
                else if (checkIsOp(c))
                {
                    if (c == "(")
                    {
                        opStack.Push(c);
                    }
                    else if (c == ")")
                    {
                        while (opStack.Count > 0)
                        {
                            var op = opStack.Peek();
                            if (op == "(")
                            {
                                opStack.Pop();
                                break;
                            }
                            else
                            {
                                reversePolish.Enqueue(opStack.Pop());
                            }
                        }
                    }
                    else
                    {
                        while (opStack.Count > 0)
                        {
                            if ("(" == opStack.Peek())
                            {
                                opStack.Push(c);
                                break;
                            }
                            else if (isGreat(opStack.Peek(), c))
                            {
                                reversePolish.Enqueue(opStack.Pop());
                            }
                            else if (isEqual(c, opStack.Peek()))
                            {
                                opStack.Push(c);
                                break;
                            }
                        }

                        if (opStack.Count == 0)
                        {
                            opStack.Push(c);
                        }
                    }
                }



            }

            // 将剩余的操作符入队
            while (opStack.Count > 0)
            {
                reversePolish.Enqueue(opStack.Pop());
            }


            Stack<TreeNode> nodeStack = new Stack<TreeNode>();

            // 将逆波兰式转化成二叉树
            while (reversePolish.Count > 0)
            {

                var s = reversePolish.Dequeue();
                // 以当前的元素的值新建一个节点
                TreeNode node = new TreeNode();
                node.value = s.ToString();
                // 如果是数字
                if (isDigitOrLetter(s))
                {

                    nodeStack.Push(node);
                    // 如果是操作符
                }
                else if (checkIsOp(s))
                {

                    //从栈里弹出两个节点作为当前节点的左右子节点
                    TreeNode rightNode = nodeStack.Pop();
                    TreeNode leftNode = nodeStack.Pop();
                    node.Left = leftNode;
                    node.Right = rightNode;
                    // 入栈
                    nodeStack.Push(node);
                }

            }

            return nodeStack.Pop();
        }

        public void Print(TreeNode root)
        {
            if (root != null)
            {
                if (checkIsOp(root.value))
                {
                    Console.Write("(");
                }
                Print(root.Left);
                Console.Write(root.value);
                Print(root.Right);
                if (checkIsOp(root.value))
                {
                    Console.Write(")");
                }

            }

        }



        private bool isDigitOrLetter(string s)
        {
            for (var i = 0; i < s.Length; i++)
            {
                if (Char.IsDigit(s[i]) || char.IsLetter(s[i]))
                {
                    return true;
                }
            }
            return false;
        }

        //private HashSet<char> opSets = new HashSet<char>(){
        //    '(',')', '|','=','&','+','*','-','/'
        //};
        private HashSet<string> opSets = new HashSet<string>(){
            "(",")", "|","=","&","+","*","-","/"
        };
        private string ptn = @"[a-zA-Z0-9_]+";


        private bool checkIsOp(string c)
        {
            return opSets.Contains(c);
        }


        private bool isGreat(string op1, string op2)
        {

            if (getPriority(op1) > getPriority(op2))

                return true;

            else

                return false;
        }

        private bool isEqual(string op1, string op2)
        {
            if (getPriority(op1) == getPriority(op2))
                return true;
            return false;
        }

        private int getPriority(string op)
        {

            if ("+" == (op) || "-" == op || op == "=")

                return 1;

            else if ("*" == op || "/" == op || op == "&" || op == "|")

                return 2;

            else

                throw new Exception("Unsupported operator!");
        }


    }

    public class TreeNode
    {
        public TreeNode Left;
        public TreeNode Right;
        public string value;
        public object ChangedData;
    }
}
